As the mobile communication becomes more ubiquitous, the bandwidth demands of wireless local area network (WLAN) also increase. In the IEEE802.11a specification, proposed to meet the demands, the Fast Fourier Transform (FFT) computation unit plays an import ant role for modulation. The FFT computation unit is able to transform the data in the time domain into corresponding data in the frequency domain. This feature allows improvement of the signal attenuation and multi-path interference problems often faced in the wireless communication. Therefore, the present and future communication specifications will continue to utilize FFT computation. However, the wireless communication hardware must be able to support the large amount of computation.
The structures of conventional FFT circuitry are categorized into three types: single-memory, dual-memory, and pipeline. The single-memory structure uses only one computation unit and utilizes the in-place computation feature of the FFT; therefore, it uses the smallest circuitry area. However, this type of structure has the disadvantage of high computational latency. The dual-memory structure uses a memory to store input and the other to store output; therefore, it provides a higher throughput than the single-memory structure. Nevertheless, it takes LogrN computation units (r, N are positive integers), and requires the largest circuitry area.
Discrete Fourier Transform (DFT) is defined as follows:
      X    ⁡          [      k      ]        =            ∑              n        =        0                    N        -        1              ⁢                  ⁢                  x        ⁡                  [          n          ]                    ⁢              w        N        kn            
Where k=0,1, . . . , N−1, n=0,1, . . . , N−1, and WN=e−j2π/N is a twiddle factor.
FIG. 1 shows a schematic view of a conventional FFT processor structure. In 2002, Lenart proposed, in “A Pipelined FFT Processor Using Data Scaling with Reduced Memory Requirements” (Proc. Of Norchip, Nov. 11-12, 2002, Copenhagen, Denmark), a pipeline structure using a base of four for FFT processor. The proposed structure takes three stages to process 64 points, and requires three multipliers and accesses the rotation factors three times. There are up to six first-in-first-out (FIFO) buffers to access in each clock.
FIG. 2 shows a schematic view of another conventional FFT processor structure. In 2003, Maharatna proposed, in “A Novel 64-Point FFT/IFFT Processor for IEEE802.11a Standard” (ICASSP 2003), FFT processor structure using a base of 8. As shown in FIG. 2, the structure processes the 64-point FFT computation by expanding two 8-based butterfly computation units and eight output units with specialized hardware connection. Although this structure reduced the latency, it requires more hardware computation units.
FIG. 3 shows a schematic view of yet another conventional FFT processor structure. In 2002, Guo proposed, in “A New Hardware-Efficient Design Approach for the 1D Discrete Fourier Transform” (Pattern Recognition and Image Analysis, Vol. 12, No. 3, 2002, pp. 299-307), a one-dimensional structure for a DFT processor. As shown in FIG. 3, the structure separates the computation of odd part and the even part, and requires a larger hardware circuitry area.
There are numerous structures for conventional FFT processors. The objects of an FFT processor are to use the least hardware area and cost, have the least time delay, and consume least energy. The aforementioned structures have the disadvantages of frequent accesses to memory, large amount of multiplication computations, and requiring a large number of computational units.